package laba1;
import java.util.NoSuchElementException;
import java.util.AbstractCollection;
import java.util.Deque;
import java.util.Iterator;

/**
 * Очередь с двусторонним доступом (дек), реализованная на двунаправленных списках.
 * Created by Михаил on 17.03.14.
 */

public class MyLinkedDeque extends AbstractCollection<Integer> implements Deque<Integer> {

    private class Node {
        public Node next;
        public Node prev;
        public Integer value;

        public Node(){
            next = null;
            prev = null;
            value = null;
        }
        public Node(int value){
            this();
            this.value = value;
        }
        public Node(Node next, Node prev, Integer value){
            this(value);
            this.next = next;
            this.prev = prev;
        }

        public Integer remove(){
            if (next != null)
                next.prev = prev;
            if (prev != null)
                prev.next = next;
            int value = this.value;
            this.value = null;
            return value;
        }
    }
    private Node firstEl;
    private Node lastEl;
    private int size;

    /**
     * Создаёт пустой дек.
     */
    public MyLinkedDeque(){
        firstEl = null;
        lastEl = null;
        size = 0;
    }

    /**
     * Создаёт дек из чисел, указанных в параметре
     * @param nodes массив целых чисел, из которых будет состоять дек (в порядке от начала к концу).
     */
    public MyLinkedDeque(int[] nodes){
        for (int nodeValue : nodes) {
            this.addLast(nodeValue);
        }
    }

    /**
     * Создаёт дек из единственного узла.
     * @param node Узел, из которого будет состоять дек.
     */
    public MyLinkedDeque(Node node){
        firstEl = node;
        lastEl = node;
        size = 1;
    }

    /**
     * Выводит элементы дека через пробел.
     * @return строка, содеражащая все элементы дека.
     */
    @Override
    public String toString() {
        String answer = "";
        for (Node cur = firstEl; cur != null; cur = cur.next)
            answer += cur.value + " ";
        return answer;
    }

    /**
     * Удаляет все элементы дека.
     */
    @Override
    public void clear() {
        while (size > 1) {
            size--;
            firstEl = firstEl.next;
            firstEl.prev.remove();
            firstEl.prev = null;
        }
        if (!isEmpty())
            firstEl.remove();
        size = 0;
        firstEl = null;
        lastEl = null;
    }

    /**
     * Добавляет элемент в начало дека.
     * @param integer целое число, которое нужно добавить.
     */
    @Override
    public void addFirst(Integer integer) {
        Node newEl = new Node(integer);
        if (size() == 0){
            firstEl = newEl;
            lastEl = firstEl;
        } else {
            firstEl.prev = newEl;
            newEl.next = firstEl;
            firstEl = newEl;
        }
        size++;
    }

    /**
     * Добавляет элемент в конец дека.
     * @param integer целое число, которое нужно добавить.
     */
    @Override
    public void addLast(Integer integer) {
        Node newEl = new Node(integer);
        if (size() == 0){
            lastEl = newEl;
            firstEl = lastEl;
        } else {
            lastEl.next = newEl;
            newEl.prev = lastEl;
            lastEl = newEl;
        }
            size++;}

    /**
     * Удаляет первый элемент дека и возвращает его.
     * @return если дек пустой - null, иначе - первый элемент дека.
     */
    @Override
    public Integer pollFirst() {
        if (isEmpty()) return null;
        Integer polled = firstEl.value;
        if (size == 1) {
            lastEl = null;
            firstEl.remove();
            firstEl = null;
        } else {
            firstEl = firstEl.next;
            firstEl.prev.remove();
        }
        size--;
        return polled;
    }

    /**
     * Удаляет последний элемент дека и возвращает его.
     * @return если дек пустой - null, иначе - последний элемент дека.
     */
    @Override
    public Integer pollLast() {
        if (isEmpty()) return null;
        Integer polled = lastEl.value;
        if (size == 1) {
            firstEl = null;
            lastEl.remove();
            lastEl = null;
        } else {
            lastEl = lastEl.prev;
            lastEl.next.remove();
        }
        size--;
        return polled;
    }

    /**
     * Показывает первый элемент дека.
     * @return если дек не пустой - первый элемент дека.
     * @throws NoSuchElementException если дек пустой.
     */
    @Override
    public Integer getFirst() throws NoSuchElementException {
        if (size() == 0)
            throw new NoSuchElementException("An attempt to call \"get\" to an empty deque.");
        else
            return firstEl.value;
    }

    /**
     * Показывает последний элемент дека.
     * @return если дек не пустой - последний элемент дека.
     * @throws NoSuchElementException если дек пустой.
     */
    @Override
    public Integer getLast() throws NoSuchElementException {
        if (size() == 0)
            throw new NoSuchElementException("An attempt to call \"get\" to an empty deque.");
        else
            return lastEl.value;
    }

    /**
     * Показывает первый элемент дека.
     * @return если дек пустой - null, иначе - первый элемент дека.
     */
    @Override
    public Integer peekFirst() {
        try {
            return getFirst();
        } catch (NoSuchElementException e) {
            return null;
        }
    }

    /**
     * Показывает последний элемент дека.
     * @return если дек пустой - null, иначе - последний элемент дека.
     */
    @Override
    public Integer peekLast() {
        try {
            return getLast();
        } catch (NoSuchElementException e) {
            return null;
        }
    }

    /**
     * Возвращает размер дека.
     * @return целое число - количество элементов в деке.
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Проверяет, есть ли элементы в деке.
     * @return если дек пустой - true, иначе - false.
     */
    @Override
    public boolean isEmpty() {
        return (size()==0);
    }

    //Unsupported

    @Override
    public Iterator iterator() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator descendingIterator() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean offerFirst(Integer integer) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean offerLast(Integer integer) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer removeFirst() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer removeLast() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeFirstOccurrence(Object o) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeLastOccurrence(Object o) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean offer(Integer integer) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer remove() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer poll() throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer element() throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer peek() throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public void push(Integer integer) throws UnsupportedOperationException  {
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer pop() throws UnsupportedOperationException {
        throw new UnsupportedOperationException();
    }
}

